1. Field of the Invention
This invention relates to a line-based halftoning process, involving the steps of:                a. performing a wavelet analysis for one row of pixels of the input image; and        b. performing a halftoning algorithm to generate the corresponding output row.The halftoning algorithm contains two main phases:        a. a top-down dot assignment phase in which dots are assigned a new luminance value based on the wavelet analysis; and        b. an error diffusion phase in which the dot assignment is compared with the original luminance value and the quantization error is diffused to the pixel in the next one or several lines.        
In the dot assignment phase, the proposed halftoning scheme adopts a dot assignment approach that mimics the results from the 1-D wavelet analysis. This is distinct from the pixel-by-pixel dot assignment approach in most existing halftoning algorithms.
In the error diffusion phase, the dot assignment is compared with the original luminance value and the quantization error diffused to the pixels in the next one or several lines (i.e. lines below the current line) as a local feedback mechanism to further improve visual quality.
Finally, post-processing techniques are employed to remove the artificial patterns.
2. Description of Related Art
Digital halftoning is a technique that renders a continuous-tone image effect on printing or display devices that can only represent a limited number of output tones. To represent each gray level, the halftoning algorithm generates a pattern of textures that, when perceived by the human viewer, has the appearance of a constant gray value. These patterns are locally modulated to represent details of the image naturally.
The following considerations must be taken into account in designing a halftoning algorithm:                A. Good visual effect. The generated image should appear to the viewer as similar to the continuous-tone original image as possible. Moreover, the good visual effect should be achieved under different level of details (LoD), which corresponding to different resolutions of the printing or the display devices.        B. Efficient implementation. In order to be implemented in real devices, it is important that the computational complexity and the memory space requirements of the algorithm are low.        
Existing digital halftoning techniques can be classified into three main categories: (1) iterative optimization, (2) dithering, and (3) error diffusion. Each of these techniques, as well as combinations of the techniques, has its own advantages and shortcomings. Generally speaking, since the iterative optimization technique demands a much higher computational cost, it is mainly of academic interest. Dithering and error diffusion are two categories that are studied more extensively as a practical approach for industrial implementation. Both approaches can be further improved to be an adaptive halftoning technique. In adaptive halftoning, the thresholds and filter weights can be adjusted according to input pixel values. A brief review of these three techniques follows.
A. Iterative Optimization
Iterative optimization methods attempt to minimize the perceived error between the continuous-tone image and the halftoned image according to some underlying models, such as the human visual system (HVS). The error is usually calculated by a weighted least square approach. Halftone images derived by this type of techniques usually have high quality at the cost of computational complexity. One example is the direct binary search addressed in D. J. Lieberman and J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Transaction of Image Processing, vol. 9, pp. 1352-1366, November 2000.
B. Dithering and Screening
Dithering provides another type of halftoning technique that adds noise to images prior to the quantization. Noise is introduced to break the monotonicity of error accumulation in the area of constant gray levels so that halftoned images are more similar to original ones. The process is shown in FIG. 1.
While white noise is a commonly known type of noise in random processes, it is not used in halftoning because it generates clustered dots, which degrades the visual quality of halftoned images. Blue noise and green noise are usually chosen in the literature of dithering, especially blue noise. One characteristic of blue noise is that it is exclusively high-frequency noise. Due to the low-pass nature of human eyes, the high frequency blue noise is least visible to the human viewer (see, R. A. Ulichney, “Digital halftoning,” MIT Press, 1987; and R. A. Ulichney, “Dithering with blue noise,” Proceedings of IEEE, vol. 76, pp. 56-79, January 1988. However, dithering with blue noise does not function well for printing devices that cannot reproduce dots consistently from dot to dot, such as laser printers. Instead, as explained in D. L. Lau, G. R. Arce, and N. C. Gallagher, “Green-noise digital halftoning,” Proceeding of IEEE, vol. 86, pp. 2424-2444, December 1998, green noise, which consists of signals in mid-frequencies. Additional details are found in D. L. Lau, R. Ulichney, and G. R. Arce, “Blue- and green-noise halftoning models,” IEEE Signal Processing Magazine, pp. 28-38, July 2003.
In practice, adding noise prior to halftoning is not an efficient approach in implementation because of the need of pseudo-random numbers, which have to be generated on-line or be stored. For this reason, it is rare to implement dithering as a direct noise adding process in industry. Instead, dithering serves as a model for understanding and has to be implemented by other algorithms that achieve the equivalent effect.
Screening, on the other hand, is a type of halftoning method that is popular in practical implementation. A screen is a matrix of thresholds applied to an image periodically. To take advantage of both screening techniques and blue and green noise, blue noise masks and green noise masks may be used, as disclosed for example in T. Mitsa and K. J. Parker, “Digital halftoning technique using a blue noise mask,” J. Opt. Soc. Amer., vol. 9, pp. 1920-1929, 1998; K. E. Spaulding, R. L. Miller, and J. Schildkraut, “Methods for generating blue-noise dither matrics for digital halftoning,” J. Electron. Imaging, vol. 6, no. 2, pp. 208-230, 1997; and D. L. Lau, G. R. Arce, and N. C. Gallagher, “Digital halftoning by means of green-noise masks,” J. Opt. Soc. Amer., vol. 16, pp. 1575-1586, July 1999. The void-and-cluster method is the most famous way to create masks, as is described in R. A. Ulichney, “The void-and-cluster method for dither array generation,” Proceeding of SPIE, Human Vision, Visual Processing, Digital Displays IV, vol. 1913, pp. 332-343, 1993. Since screening is a low complexity halftoning technique, it is commonly used in industry (see, U.S. Pat. No. 5,726,772).
C. Error Diffusion
The error diffusion approach was first proposed by R. W. Floyd and L. Steinberg in “An adaptive algorithm for spatial grey scale,” Proceedings of Society of Information Display International Symposium Digest of Technical Papers, pp. 36-37, March 1975. The basic idea is to take care of errors introduced in the quantization process using a self-correcting feedback system. Errors are diffused to unprocessed neighbor pixels. The error diffusion process is shown in FIG. 2.
When viewed by humans, halftone images generated by error diffusion appear to be more similar to original ones. The textures are smoother. However, error diffusion does leave some artifacts such as moiré patterns and the directional hysteresis. The moiré pattern is the result of superimposing regular patterns on an image. To overcome the unpleasant moiré pattern, the size of error diffusion filters is enlarged and different weight values are assigned, as disclosed for example in J. Jarvis and C. Roberts, “A new technique for displaying continuous tone images on a bilevel display,” IEEE Transactions on Communications, pp. 891-898, August 1976; J. Jarvis, C. Judice, and W. Ninke, “A survey of techniques for the display of continuous tone pictures on bilevel displays,” Computer Graphics and Image Processing, vol. 5, pp. 13-40, 1976; and P. Stucki, “Meccaxa multiple-error correcting computation algorithm for bilevel hardcopy reproduction,” Research Report RZ1060, IBM Research Laboratory, 1981. Another way to reduce artifacts is to use a serpentine scan instead of the raster scan, as described in R. A. Ulichney, “Dithering with blue noise,” Proceeding of IEEE, vol. 76, pp. 56-79, January 1988; and I. Witten and R. Neal, “Using peano curves for bilevel display of continuous-tone images,” IEEE Computer Graphics and Applications, pp. 47-51, May 1982.
D. Adaptive Techniques
Dithering, screening, and error diffusion have recently been enhanced to be adaptive to the content of images. Generally speaking, adaptivity is achieved by making thresholds and filter weights variable. To achieve adaptation, several factors are considered: (1) pixel values, (2) edge behaviors and (3) human visual systems (HVS).
Since halftoning changes an image from the gray scale to a binary scale, edge behaviors between input and output images become different. Consistency has therefore been a focus of research in the area of adaptive halftoning techniques. By testing different filters adopted by error diffusion, Z. Fan and F. Li (“Edge behavior of error diffusion,” Proceedings of IEEE International Conference on Image Processing, pp. 113-116, October 1995) discovered that, while most of the time edges are enhanced, they are blurred sometimes. Thus, they proposed a nonlinear edge enhancement technique, where HVS factors are used to exploit the low-pass characteristics of human eyes.
There is work about adaptive halftoning based on the least squares error criterion with HVS. In that case, the halftoning is adjusted according to local pixel values, as disclosed in H. Nishida, “Adaptive model-based digital halftoning incorporating image enhancement,” Proceedings of 15th International Conference on Pattern Recognition, vol. 3, pp. 306-309, September 2000. In the method disclosed in U.S. Pat. No. 6,760,126, a pixel is dithered twice with two different masks and has two temporary outputs, which are combined according to edge activities and suppression parameters. In this way, the method is adaptive to images with both low and high activities. Since dithering is not a mainstream halftoning technique, there is relatively little work on adaptive dithering in the literature.
There exists more work on adaptive error diffusion, either with several fixed filters or with tone-dependent filters. U.S. Pat. Nos. 5,737,453 and 6,356,362 proposed a method that applies several different matrices according to gray values, for example, a two-term matrix for extreme gray levels and a four-term matrix for midtones. Matrices in midtone-to-extreme gray level transitions are obtained by interpolation. The error diffusion approach was enhanced based on the HVS and the edge behavior described in U.S. Pat. No. 6,563,957 and P. Li and J. P. Allebach, “Tone-dependent error diffusion,” IEEE Transactions on Image Processing, vol. 13, no. 2, pp. 201-215, February 2004. A tone dependent threshold was developed so that the edge effect and the start-up delay can be reduced.
A parallel scan with variable weights has also adopted to reduce artifacts. P. W. Wong (“Adaptive error diffusion and its application in multiresolution rendering,” IEEE Transaction on Image Processing, vol. 5, no. 7, pp. 1184-1196, July 1996) considered more than one fixed error diffusion filter, where the filters were adjusted during the halftoning process. The objective is to minimize the error, and the implementation is done using the least mean squares (LMS) algorithm from adaptive signal processing. Another advantage of P. D. Wong's work, described in P. W. Wong, “Adaptive error diffusion and its application in multiresolution rendering,” IEEE Transaction on Image Processing, vol. 5, no. 7, pp. 1184-1196, July 1996, is that it can offer multi-resolution rendering.
Using either dithering or error diffusion technique alone has some shortcomings. The halftoning method described in U.S. Pat. No. 5,970,178 attempts to use advantages of both approaches. Regions are evaluated by some methods first. If the region is “busy” and “rich”, i.e. with detailed information, the error diffusion method is applied. Otherwise, a smooth dithering method is used. Adaptive halftoning with error diffusion can also be achieved with variable dot sizes, as described in U.S. Pat. No. 6,778,299.
There are studies on adaptive thresholds such as those described in N. Damera-Venkata and B. L. Evans, “Adaptive threshold modulation for error diffusion halftoning,” IEEE Transactions on Image Processing, vol. 10, no. 1, pp. 104-116, January 2001; and U.S. Pat. No. 5,268,774. In the Damera-Venkata and Evans article, the quantization process was modeled implicitly so that a wide variety of quantizers can be used. In the method described in U.S. Pat. No. 5,268,774, the dither pattern, the pixel value, pixel values and an edge enhancement technique are used to decide the threshold value. A survey on the improvement of error diffusion using different threshold modulation schemes is given in R. Eschbach, Z. Fan, K. T. Knox, and G. Marcu, “Threshold modulation and stability in error diffusion,” IEEE Signal Processing Magazine, pp. 39-50, July 2003.
Although adaptive halftoning techniques provide more pleasant visual results, their actual effects vary from printer to printer. This is because printers have different printing capabilities, dot sizes and dot shapes. For example, some laser printers have a problem in printing dots consistently from one to the other. Other phenomena common to most printing devices are dot overlap and dot gain. Printers may produce some circular dots that overlap adjacent ones, which is called the dot overlap effect. Furthermore, printers may produce dots that appear larger than required, which is called the dot gain. These concepts are illustrated in FIG. 3. Consequently, it is important to study halftoning techniques based on the printing model, as described for example in U.S. Pat. No. 5,592,592; T. N. Pappas and Neuhoff, “Least-squares model-based halftoning,” IEEE Transactions on Image Processing, vol. 8, no. 8, pp. 1102-1116, August 1999; and T. N. Pappas, J. P. Allebach, and D. L. Neuhoff, “Model-based digital halftoning,” IEEE Signal Processing Magazine, pp. 14-27, July 2003.
D. Color Halftoning
In addition to the halftoning techniques discussed above, which are for gray-scale images, halftoning techniques for color images are important too. There exist more than on color image system, each with multiple colorant planes, such as the CMYK (cyan, magenta, yellow, and black) or the RGB (red, green and blue) systems. The error diffusion technique developed for gray scale halftoning cannot be applied to color images directly since human eyes have different sensitivities to different frequencies of different colorant planes. Therefore, while each colorant channel should be considered separately, the interaction between different channels must be examined as well. Issues of color halftoning are addressed in J. L. Mitchell, G. Thompson, and C. W. Wu, “Multilevel color halftoning,” IBM Research Report, December 2001; U.S. Pat. No. 6,501,564, December 2002; and N. Damera-Venkata, B. L. Evans, and V. Monga, “Color error-diffusion halftoning,” IEEE Signal Processing Magazine, pp. 51-58, July 2003.
F. Multi-resolution Approach
The final two categories of halftoning techniques are wavelet-based and multi-resolution-based halftoning techniques. The wavelet transform has been used in inverse halftoning, as described in Z. Xiong, M.T. Orchard, and K. Ramchandran, “Inverse halftoning using wavelets,” IEEE Transaction on Image Processing, vol. 8, no. 10, pp. 1479-1483, October 1999; R. Neelamani, R. Nowak, and R. Baraniuk, “Model-based inverse halftoning with wavelet-vaguelette deconvolution,” Proceedings of 2000 IEEE International Conference on Image Processing, vol. 3, pp. 973-976, September 2000; and C. Kuo, A. Ravishankar Rao, and G. Thompson, “Wavelet based halftone segmentation and descreening filter design,” Proceedings of 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 3, pp. 1573-1576, May 2001. Inversed halftoning converts a two-tone image to a continuous-tone image. A new approach to inverse halftoning using non-orthogonal wavelets is addressed in Z. Xiong, M.T. Orchard, and K. Ramchandran, “Inverse halftoning using wavelets,” IEEE Transaction on Image Processing, vol. 8, no. 10, pp. 1479-1483, October 1999. This technique is sometimes called descreening or unscreening (See, U.S. Pat. Nos. 5,799,112 and 6,738,524.
The wavelet transform has also been used in the preprocessing stage as described in H. Szu, Y. Zhang, M. Sun, and C.-C. Li, “Neural network adaptive digital image screen halftoning (dish) based on wavelet transform preprocessing,” SPIE Proceeding, vol. 2242, pp. 963-966, April 1994; and H. Szu, Y. Zhang, M. Sun, and C.-C. Li, “Neural network adaptive digital image screen halftoning (dish) based on wavelet transform preprocessing,” Proceedings of 1993 International Joint Conference on Neural Networks (IJCNN), vol. 2, pp. 1215-1218, October 1993. Since the wavelet transform provides a mechanism to achieve both spatial and frequency localization, it is a good tool for image analysis. The wavelet transform is used to find the frequency information, which is further utilized to control the screening function.
The method described in the Szu et al. articles uses two-dimensional wavelet transform as well as the neural network technology. Thus, it demands a large storage space and a significant amount of computation. The present invention also uses wavelet analysis, but the approach is very different from theirs. Only the one-dimensional wavelet transform is applied in the algorithm of the invention. Furthermore, the wavelet analysis of the invention is used for dot assignment rather than screening function control.
There are a few papers on multi-resolution halftoning, including P.W. Wong, “Adaptive error diffusion and its application in multiresolution rendering,” IEEE Transaction on Image Processing, vol. 5, no. 7, pp. 1184-1196, July 1996; and I. Katsavounidis and C.-C. Jay Kuo, “A multiscale error diffusion technique for digital halftoning,” IEEE Transaction on Image Processing, vol. 6, no. 3, pp. 483-490, March 1997. The multi-resolution halftoning concept was introduced to create halftones, and a multiscale error diffusion process was proposed in H. Szu, Y. Zhang, M. Sun, and C.-C. Li, “Neural network adaptive digital image screen halftoning (dish) based on wavelet transform preprocessing,” SPIE Proceeding, vol. 2242, pp. 963-966, April 1994, and in the Katsavounidis and Kuo article. First, it demands a two-dimensional processing which demands a large memory space. Second, it uses the pixel-by-pixel dot assignment scheme, which is not very efficient. Another multi-resolution method was discussed in [23].
The algorithm of the present invention uses both the wavelet transform and multi-scale dot assignment concepts. However, it is different from previous work in the following aspects. The halftoning process is line-based and dots are assigned in a top-down fashion. Error diffusion is also adopted to fine tune the halftoned images to compensate errors generated by the implicit quantization. The 1-D processing makes the implementation easy while the top-down multiscale dot assignment can produce a multi-resolution halftoned image, which provides a good approximation of the original in multiple scales.